package cn.edu.anan.algorithm.sort;

/**
 * 排序算法描述
 */
public class SortDesc {

    /**
     * 常用的经典排序算法8种：
     *  1.时间复杂度O(n^2)：
     *      冒泡排序、插入排序、选择排序
     *  2.时间复杂度O(nLogn)：
     *      快速排序、归并排序
     *  3.时间复杂度O(n)：
     *      桶排序、计数排序、基数排序
     */

    /**
     * 分析排序算法的三个角度：
     *  1.算法的执行效率
     *      1.1.最好情况、最坏情况、平均情况时间复杂度
     *      1.2.时间复杂度的系数、常数、低阶需要考虑
     *  2.算法的内存消耗
     *      2.1.原地排序算法：空间复杂度是O（1）的排序算法
     *  3.算法的稳定性
     *      3.1.稳定排序算法：如果待排序的序列中，存在值相等的元素，
     *      那么经过排序之后，相等元素之间原有的顺序保持不变
     */

    /**
     * 数学基础知识：
     *  1.有n个元素，每两个元素组成一个组合，总共有n(n-1)/2个组合数
     *  2.有n个元素，每两个元组组成一个排列，总共有n!个排列数
     */

    /**
     * 排序常识概念：
     *  1.有序度：如果下标索引i<j，且a[i] <a[j] 则满足有序度
     *  2.逆序度：如果下标索引i<j，且a[i]>a[j] 则满足逆序度
     *  3.满有序度：如果有序度=n(n-1)/2，则满足满有序度
     *  4.我们整个排序过程：就是要增加有序度，减少逆序度，最终达到满有序度
     */

}
